Hi, inspiered by this HN thread I decided to write about some of the most influential computer science papers I have read. For me, these papers shaped what I think computer science is, and what it can be. When someone asks me “What is computer science?” I think the awnser is that is is the scientific investiagtion of IT. On the low end are foundational papers whoose results are used, remixed and relevant to this day. On the high end are papers that are visionary, and have shaped the way we think about computer science, that have inspiered novel ways of thinking.

Often, computer science is seen as beeing about programming, but I think that is a narrow view. Programming is a tool, but if there were a better tool, we would use that. Programming can be a tool for buissines applications, but it can also be a tool for computer science. Programmim is rooted in cs, but there is more to cs than investiagting programming or appliying programming. Think of innovations like online banking, generative ai, or avatar (the movies), programming was a part of it, but the real hard work to enable these things is not coding, but rather networking, security, neural networks, etc.

What makes a paper goated?

Andreas Zeller reccomends to:

do work that is relevant
strive for simplicity
keep innovating and I think these are great guidelines. To do relevant work means to look at the world and identify how the world can be improved most effectivly. A simple approach is easy to understand, and easy to build upon, thus making it more likely to be used. Innovation is creation of new ideas. Not only should we innovate, but we should keep innovating. Consistenty coming up with novel ideas is hard, but it is what drives the field forward.

For me, I think a paper is goated if it is foundational and practical while being simple and visionary. Bonus points if it is vivid.

Shannon’s A Mathematical Theory of Communication

Shannon paved the way for modern cryotography, and is the father of information theory. In this paper, Shannon introduces the concept of entropy, which is a measure of the uncertainty of a random variable.

Venevar Bush’s As We May Think

Bush was a military scientist, and in this paper he describes a machine, the Memex, that is a precursor to the modern computer. He describes a machine that can store and retrieve information, and that can be used to solve complex problems.

Noam Chomsky’s Three Models for the Description of Language

Chomsky is a linguist, and in this paper he describes three models for the description of language. He describes the generative model, the transformational model, and the interpretive model. He argues that the generative model is the most powerful, and that it is the model that is used by humans to generate and understand language. Chomsky is an interesting intellectual.

Richard Hamming’s You and your research

You gotta read or listen to this one.

Diffie and Hellman’s New Directions in Cryptography

Diffie and Hellman brought up real innovation here. They had a vision about how powerful public key cryptography can be and they developed the first public key cryptosystem. They invented the Diffie-Hellman key exchange protocol, which enables the secure exchange of cryptographic keys over a public channel. Their work combines practical applications with theoretical insights, as well as beeing relativly vivid and easy to understand.

Rivest, Shamir, and Adleman’s A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

Rivest and Shamir set out to give counterexamples to the vision of Diffie and Hellman, but ended up finding a way to make it work. Together with Adleman, they developed the RSA cryptosystem. RSA also combines practical applications with theoretical insights. RSA is relativly simple and can be vividly explained, its security guarantees are interesing to analyze, and it is still used today.

Saltzer and Schroeder’s The Protection of Information in Computer Systems

This one is goated. Salzer and Schroeder propose principles for secure system design.

Joux’s A One Round Protocol for Tripartite Diffie-Hellman

Joux extends the Diffie-Hellman key exchange protocol to three parties. It uses pairing based cryptography, which is a powerful tool for secure multi-party computation. His work is vivid, innovative and has practical applications.

Satoshi Nakamoto’s Bitcoin: A Peer-to-Peer Electronic Cash System

The anaonymous Satoshi Nakamoto developed the first decentralized cryptocurrency. He started with this paper, based on the ideas from RSA and Chaum.

Ken Thompson’s Reflections on Trusting Trust

This paper came out of Thompson winning the Turing award. He describes a backdoor put into the compiler to produce binaries that contain the backdoor.

Anne Adams and Martina Angela Sasse’s Users are not the enemy

This paper is about usable security. Sasse founded the field of usable security, and this paper is a foundational work in that field. Another noteworth paper is “Why Johnny can’t encrypt” by Alma Whitten and J.D. Tygar. Johnny has been a recurring character in security papers.

Dijkstra’s A Note on Two Problems in Connexion with Graphs

Dijkstra is a pioneer in algorithms. He invented the shortest path algorithm, which is used in many applications, such as routing in computer networks. In this paper, he describes two problems related to graphs: the shortest path problem and the minimum spanning tree problem. He presents algorithms to solve these problems, which are based on the idea of dynamic programming. Dynamic programming is a powerful tool, it is op.

Bloom’s Space/Time Trade-offs in Hash Coding with Allowable Errors

Bloom invented the bloom filter, which is a probabilistic data structure that can be used to test whether an element is a member of a set. It is a simple and efficient data structure that has many practical applications. For example, it is used in network routers to filter out unwanted traffic or in databases to speed up queries.

Moore’s Cramming more components onto integrated circuits

Mopre’s the co-founder of Intel, this is the original “Moore’s Law” paper.

Patterson and Hennessy’s Computer Architecture: A Quantitative Approach

Patterson and Hennessy are the authors of this textbook covering computer architecture. Hennessy is a former president of Stanford University. Patterson and Hennessy won the Turing award for their work on RISC.

Google’s MapReduce: Simplified Data Processing on Large Clusters

In this paper, Google describes the MapReduce programming model, which is a simple and efficient way to process large amounts of data on a cluster of computers. MapReduce is based on functional programming and consits of two functions: map and reduce. This model is executed on lists, first the map function transforms each element of the lists, which can be done in parallel, and then the reduce function is applied to the transformed elements to produce the final result, which is done in series.

James Kajiya’s Rendering Equation

This is a foundational paper in computer graphics. Kajiya describes a physically based rendering equation that models the interaction of light with surfaces. Finding ways to solve this equation cheaply is a major challenge in computer graphics.

Dijkstra’s Go To Statement Considered

Dijkstra argues that the goto statement is harmful, because it makes programs harder to understand and maintain. He proposes structured programming as an alternative, which uses loops and conditionals instead of gotos.

The Art of Computer Programming by Donald Knuth

Knuth is very influential. His book sieries “The Art of Computer Programming” is a classic. He invented tex and metafont to typeset his books.

Here is a funny video of him mishearing a question about a teacher as t-shirt: https://www.youtube.com/watch?v=74BfHoE66rc&t=2537s Knuth is famous for sending checks over $2.56 to people who find errors in his books.